package _base0to1;

import java.util.ArrayList;

/**
 * 706. 设计哈希映射
 */
public class No706 {
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    public No706() {
        int size = 7;
        // 初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        this.size = size;
        // ？留一个坑，这时不要忘记分别初始化每个链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    public void put(int key, int value) {
        Emp emp = new Emp(key, value);
        // 根据员工的id，得到该员工应当添加到哪条链表
        int empLinkedListArrayNo = hashFund(emp.id);
        // 将emp 添加到对应的链表中
        empLinkedListArray[empLinkedListArrayNo].add(emp);
    }

    public int get(int key) {
        // 根据员工的id，得到该员工应当到哪条链表查找
        int empLinkedListArrayNo = hashFund(key);
        // 将到对应的链表中查找 emp
        Emp emp = empLinkedListArray[empLinkedListArrayNo].findById(key);
        return emp == null ? -1 : emp.name;
    }

    public void remove(int key) {
        // 根据员工的id，得到该员工应当到哪条链表查找
        int empLinkedListArrayNo = hashFund(key);
        empLinkedListArray[empLinkedListArrayNo].del(key);
    }

    /**
     * 编写散列函数，使用一个简单取模法
     */
    private int hashFund(int id) {
        return id % size;
    }

    /**
     * 表示一个雇员
     */
    class Emp {
        public int id;
        public int name;
        public Emp next;

        public Emp(int id, int name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Emp{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

    /**
     * 创建EmpLinkedList，表示链表
     */
    class EmpLinkedList {
        /**
         * 头指针，执行第一个Emp，因此我们这个链表的head 是指向第一个Emp
         */
        private Emp head;

        /**
         * 添加雇员到链表
         * 说明
         * 1.假定，当添加雇员时，id 是自增长，即id的分配总是从小到大
         * 因此我们将该雇员直接加入到本链表的最后即可
         */
        public void add(Emp emp) {
            // 如果是第一个
            if (head == null) {
                head = emp;
                return;
            }
            //否则
            Emp curEmp = head;
            while (true) {
                if (curEmp.id == emp.id) {
                    curEmp.name = emp.name;
                    return;
                }
                if (curEmp.next == null) {
                    break;
                }
                curEmp = curEmp.next;
            }
            curEmp.next = emp;
        }

        /**
         * 遍历链表的雇员信息
         */
        public void list(int no) {
            if (head == null) {
                System.out.println("第 " + (no + 1) + " 链表为空");
                return;
            }
            //否则
            System.out.print("第 " + (no + 1) + " 链表为 ");
            Emp curEmp = head;
            while (true) {
                System.out.printf("=> id=%d name=%s\t", curEmp.id, curEmp.name);
                if (curEmp.next == null) {
                    break;
                }
                curEmp = curEmp.next;
            }
            System.out.println();
        }

        /**
         * 根据id查找雇员
         */
        public Emp findById(int id) {
            if (head == null) {
                return null;
            }
            //否则
            Emp curEmp = head;
            while (true) {
                if (curEmp.id == id) {
                    return curEmp;
                }
                if (curEmp.next == null) {
                    return null;
                }
                curEmp = curEmp.next;
            }
        }

        /**
         * 删除节点的信息，根据no编号来删除。
         * 说明
         * 1.head 不能动，因此我们需要一个temp辅助节点找到待删除的前一个节点
         * 2.说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
         */
        public void del(int no) {
            //判断是否为空
            if (head == null) return;
            //如果要删除的节点是头节点
            if (head.id == no) {
                head = head.next;
                return;
            }
            Emp temp = head;
            //遍历链表，找到最后
            while (true) {
                //说明temp已经在链表的最后
                if (temp.next == null) {
                    break;
                }
                //说明编号存在
                if (temp.next.id == no) {
                    temp.next = temp.next.next;
                    break;
                }
                //如果没有找到最后，就将temp后移
                temp = temp.next;
            }
        }
    }
}
